package com.cjx.leetcode.backtracking;

import java.util.Base64;

/**
 * @author cjx
 * @description E37.解数独【难】
 * @createDate 2024/4/9 16:50
 **/
public class E37 {
    public void solveSudoku(char[][] board) {
        backtracking(board);
    }

    private boolean backtracking(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                //不为空不可写入
                if (board[i][j] != '.') {
                    continue;
                }
                //寻找一个可写入的数值
                for (char k = '1'; k <= '9'; k++) {
                    if (isWrite(k, board, i, j)) {
                        board[i][j] = k;
                        if (backtracking(board)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    private boolean isWrite(char writeChar, char[][] board, int row, int col) {
        for (int i = 0; i < 9; i++) {
            //判断这一行是否包含此值
            if (board[row][i] == writeChar) {
                return false;
            }
            //判断这一列是否包含此值
            if (board[i][col] == writeChar) {
                return false;
            }
        }
        //判断9宫格内是否包含此值
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == writeChar) {
                    return false;
                }
            }
        }
        return true;
    }


}
